import java.util.HashMap;
import java.util.Map;
//最长的斐波那契子序列的长度
//测试链接：https://leetcode.cn/problems/length-of-longest-fibonacci-subsequence/
public class LenLongestFibSubseq {
    public int lenLongestFibSubseq(int[] arr) {
        // 优化：将 数组中的元素 + 下标 绑定在⼀起，扔到哈希表中
        Map<Integer, Integer> hash = new HashMap<Integer, Integer>();
        int n = arr.length;
        for (int i = 0; i < n; i++)
            hash.put(arr[i], i);
        int[][] dp = new int[n][n];
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++)
                dp[i][j] = 2;

        int ret = 2;
        for (int j = 2; j < n; j++) // 固定最后⼀个数
            for (int i = 1; i < j; i++) // 枚举倒数第⼆个数
            {
                int a = arr[j] - arr[i];
                if (a < arr[i] && hash.containsKey(a))
                    dp[i][j] = dp[hash.get(a)][i] + 1;
                ret = Math.max(ret, dp[i][j]);
            }
        return ret < 3 ? 0 : ret;
    }
}
